package algorithm.sort;

import util.ListUtil;

import java.util.Arrays;
import java.util.Random;

/**
 * @File Info: leetcode -- <Sort>
 * @Author: 18362
 * @Create: 2022-03-05 13:15:54 星期六
 */
public class Sort {

    private static Random random = new Random(System.currentTimeMillis());
    private static final int MAX_BOUND = 30000;
    private static final int ARRAY_SIZE = 20;

    private static void swap(int[] nums, int i, int j) {
        if (i == j)
            return;
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void selectSort(int[] nums) {
        int len = nums.length;
        for(int i=0; i<len; ++i) {
            int minIndex = i;
            for(int j=i+1; j<len; ++j) {
                if (nums[j] < nums[minIndex])
                    minIndex = j;
            }
            swap(nums, minIndex, i);
        }
    }

    public static void insertSort(int[] nums) {
        int len = nums.length;
        for(int i=0; i<nums.length; ++i) {
            int target = nums[i];       // 将target插入前面的有序序列中
            int j = i-1;
            while (j>=0) {
                if (nums[j] > target)
                    nums[j+1] = nums[j];
                else
                    break;
                j--;
            }
            nums[j+1] = target;
        }
    }

    public static void bubbleSort(int[] nums) {
        int len = nums.length;
        for(int i=0; i<len; ++i) {
            boolean flag = false;
            for(int j=len-1; j>i; j--) {
                if (nums[j] < nums[j-1]) {
                    flag = true;
                    swap(nums, j, j-1);
                }
            }
            if (!flag)
                break;
        }
    }

    public static void quickSort(int[] nums) {
        shuffle(nums);      // 随机打乱，防止陷入最坏复杂度
        quickSortHelper(nums, 0, nums.length-1);
    }

    private static void shuffle(int[] nums) {
        for(int i=0; i<nums.length; ++i)
            swap(nums, i, i + random.nextInt(nums.length-i));
    }

    private static void quickSortHelper(int[] nums, int left, int right) {
        if (left >= right)
            return;
        int mid = partition(nums, left, right);
        quickSortHelper(nums, left, mid-1);
        quickSortHelper(nums, mid+1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        if (left == right)
            return left;
        int pivot = nums[left];
        while (left < right) {
            while (left<right && nums[right]>=pivot)
                right--;
            nums[left] = nums[right];
            while (left<right && nums[left]<=pivot)
                left++;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }

    public static void mergeSort(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSortHelper(nums, 0, nums.length-1, temp);
    }

    private static void mergeSortHelper(int[] nums, int left, int right, int[] temp) {
        if (left >= right)
            return;
        int mid = left + (right - left) / 2;
        mergeSortHelper(nums, 0, mid, temp);
        mergeSortHelper(nums, mid+1, right, temp);
        merge(nums, left, mid, right, temp);
    }

    private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        int i = left, j = mid+1, k = 0;
        while (i <= mid && j<=right) {
            if (nums[i] <= nums[j])
                temp[k++] = nums[i++];
            else
                temp[k++] = nums[j++];
        }
        while (i <= mid)
            temp[k++] = nums[i++];
        while (j <= right)
            temp[k++] = nums[j++];
        System.arraycopy(temp, 0, nums, left, k);
    }

    public static void heapSort(int[] nums) {
        // 初始化堆，大顶堆，因为要从小到大排序
        for(int top = nums.length/2-1; top >= 0; top--)
            ajustHeap(nums, top, nums.length-1);
        for(int bottom=nums.length-1; bottom>0; bottom--) {
            swap(nums, 0, bottom);
            ajustHeap(nums, 0, bottom-1);
        }
    }

    /**
     * 将[top, bottom]调整为大顶堆
     */
    private static void ajustHeap(int[] nums, int top, int bottom) {
        int base = nums[top];
        for(int k=top*2 + 1; k <= bottom; k=2*k+1) {
            if (k+1 <= bottom && nums[k+1] > nums[k])
                k++;
            if (nums[k] > base) {
                nums[top] = nums[k];
                top = k;
            } else
                break;
        }
        nums[top] = base;
    }

    public static void radixSort(int[] nums) {
        if (nums.length <= 1)
            return;
        // 基数是10，根据最大值求位数最多是多少
        int digits = getMaxDigits(nums);
        int[] temp = new int[nums.length], count = new int[10];
        for (int k = 0; k < digits; k++) {
            for (int i = 0; i < nums.length; i++)
                count[getDigitOfValue(nums[i], k)]++;
            for (int i=1; i<count.length; ++i)
                count[i] += count[i-1];
            for (int i = nums.length-1; i >=0; --i) {
                int digit = getDigitOfValue(nums[i], k);
                count[digit]--;
                temp[count[digit]] = nums[i];
            }
            System.arraycopy(temp, 0, nums, 0, nums.length);
            Arrays.fill(count, 0);
        }
    }

    private static int getMaxDigits(int[] nums) {
        int maxNum = nums[0];
        for(int i=1; i<nums.length; ++i)
            maxNum = Math.max(nums[i], maxNum);
        int digits = 0;
        while (maxNum > 0) {
            digits++;
            maxNum /= 10;
        }
        return digits;
    }

    /**
     * 返回num的第k位，最低位对应的k是0
     * 比如getDigitOfValue(12345, 1)=4
     */
    private static int getDigitOfValue(int num, int k) {
        for(int i=0; i<k; ++i)
            num /= 10;
        return num % 10;
    }


    public static void main(String[] args) {
        int[] nums = new int[ARRAY_SIZE];
        for(int i=0; i< nums.length; ++i) {
            nums[i] = random.nextInt(MAX_BOUND);
        }
        ListUtil.printIntArray(nums);
//        selectSort(nums);
//        insertSort(nums);
//        bubbleSort(nums);
        quickSort(nums);
//        mergeSort(nums);
//        heapSort(nums);
//        radixSort(nums);
        ListUtil.printIntArray(nums);
    }
}
